/**
 * ArrayLength.java created by zhangzhidong 
 * at 下午10:14:02 2016年4月21日
 */
package algorithm.CIG.array;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangzhidong
 *
 */
public class ArrayLength extends ArrayBase {
	public static int getMaxLength(int arr[],int k){
		if(checkArray(arr)){
			Map<Integer,Integer> map = new HashMap<Integer,Integer>();
			map.put(0,-1);
			int len = 0;
			int right = 0;
			int sum = 0;
			while(right<arr.length){
				sum+=arr[right];
				if(!map.containsKey(sum)){
					map.put(sum, right);
				}
				len = Math.max(len, map.containsKey(sum-k)?(right-map.get(sum-k)):len);
				
				right ++;
			}
			return len;
		}else  return 0;
	}
	
	public static int getMaxLengthPositive(int array[] ,int k){
		if(array == null | array.length==0){
			return 0;
		}
		int left = 0;
		int right = 0;
		int len = 0;
		int sum = array[0];
		while(right<array.length){
			if(sum==k){
				len = Math.max(len, right-left+1);
				sum-=array[left++];
			}else if (sum<k){
				right ++;
				if(right == array.length){
					break;
				}else{
					sum+=array[right];
				}	
			}else{
				sum-=array[left++];
			}
		}
		return len;
	}
	public static void main(String args[]){
//		System.out.println(getMaxLengthPositive(generateArray(), 3));
		System.out.println(getMaxLength(new int[]{1,2,3,3,1,-1,1,1,1}, 10));
	}
}
